package com.my.study.structures.sort;

/**
 * 堆排序
 * 
 * @author Carlos
 * @version 1.0.0
 * @date 2023/2/20 21:38
 */
public class HeapSort {

    public static void main(String[] args) {
        int[] a = {20, 30, 90, 40, 70, 110, 60, 10, 100};
        
        heapSortDesc(a);


        System.out.println(a);
        
    }
    
    
    private static void heapSortAsc(int[] a) {
        int n,i;
        n = a.length;
        
        for(i = n / 2 - 1; i >= 0; i--) {
            maxHeapDown(a, i, n - 1);
        }
        
        for(i = n -1; i > 0; i--) {
            int temp = a[i];
            a[i] = a[0];
            a[0] = temp;
            maxHeapDown(a, 0, i - 1);
        }
    }
    
    
    private static void maxHeapDown(int[] a, int start, int end) {
        // 当前节点
        int c = start;
        // 左孩子节点
        int l = 2 * c + 1;
        int parent = a[c];

        for (; l <= end; c = l, l = 2 * l + 1) {
            // 右孩子节点 大于 左孩子节点
            if (l < end && a[l] < a[l+1]) {
                l++;
            }
            // 父节点 大于 左右孩子
            if (parent > a[l]) {
                // 调整结束
                break;
            }
            else {
                a[c] = a[l];
                a[l] = parent;
            }
        }
    }

    private static void heapSortDesc(int[] a) {
        int n,i;
        n = a.length;

        for(i = n / 2 - 1; i >= 0; i--) {
            minHeapDown(a, i, n - 1);
        }

        for(i = n -1; i > 0; i--) {
            int temp = a[i];
            a[i] = a[0];
            a[0] = temp;
            minHeapDown(a, 0, i - 1);
        }
    }
    
    private static void minHeapDown(int[] a, int start, int end) {
        // 当前节点
        int c = start;
        // 左孩子节点
        int l = 2 * c + 1;
        int parent = a[c];

        for (; l <= end; c = l, l = 2 * l + 1) {
            // 左孩子节点 大于 右孩子节点
            if (l < end && a[l] > a[l+1]) {
                l++;
            }
            // 父节点 小于 左右孩子
            if (parent <= a[l]) {
                // 调整结束
                break;
            }
            else {
                a[c] = a[l];
                a[l] = parent;
            }
        }
    }
    
    
}
